#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void print_dp(vector<vector<int>> &dp, int l1, int l2)
{
    for (int i = 0; i < l1; i++)
    {
        for (int j = 0; j < l2; j++)
        {
            if (dp[i][j] == INT_MIN / 2)
                cout << "inf";
            else
                cout << dp[i][j];
            cout << "\t";
        }
        cout << endl;
    }
}

class Solution
{
public:
    int maxSum(const vector<int> &nums, int k, int m)
    {
        int n = nums.size();
        vector<int> s(n + 1);
        partial_sum(nums.begin(), nums.end(), s.begin() + 1); // 前缀和

        vector<vector<int>> f(k + 1, vector<int>(n + 1, INT_MIN / 2));
        f[0] = vector<int>(n + 1, 0);
        for (int i = 1; i <= k; i++)
        {
            int mx = INT_MIN;
            // 左右两边留出足够空间给其他子数组
            for (int j = i * m; j <= n - (k - i) * m; j++) {
                // mx 表示最大的 f[i-1][L]-s[L]，其中 L 在区间 [(i-1)*m, j-m] 中
                mx = max(mx, f[i - 1][j - m] - s[j - m]);
                f[i][j] = max(f[i][j - 1], mx + s[j]); // 不选 vs 选
            }
        }
        int res = f[k][n];
        cout << "res:\t" << res << endl;
        return res;
    }
};

int main()
{
    (Solution()).maxSum({1, 2, -1, 3, 3, 4}, 2, 2);
    (Solution()).maxSum({-10, 3, -1, -2}, 4, 1);
    return 0;
}
